package leetcode.tree.binary.path;

import leetcode.tree.binary.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 508. 出现次数最多的子树元素和
 *
 */
public class FindFrequentTreeSum {

    // 保存所有子树和的List
    private final List<Integer> list = new ArrayList<>();

    public static void main(String[] args) {
        Integer[] arr = {1, 2, 3, 4, 5, 6, 7, 8};
        // 构建二叉排序树(完全二叉树)
        TreeNode tree = TreeNode.createTreeByArr(arr);

        FindFrequentTreeSum solution = new FindFrequentTreeSum();
        solution.findFrequentTreeSum(tree);

        System.out.println(solution.list);
    }

    public int[] findFrequentTreeSum(TreeNode root) {
        treeSum(root);
        return null;
    }

    /**
     * 递归求各个子树的和
     *
     * @param root 子树
     * @return
     */
    public int treeSum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftSum = treeSum(root.left);
        int rightSum = treeSum(root.right);
        int sum = root.val + leftSum + rightSum;
        list.add(sum);
        return sum;
    }
}
